前言

昨天介紹的Balanced Search Tree是為了改善不平衡的Binary Search Tree的搜尋速度。
今天介紹一個搜尋速度很快的資料結構 - Hash Table。

Hash

• 筆者的朋友分享了對Hash的理解:

Hash 是 雜湊
Potato 是 馬鈴薯
Hash Potato 就變成 薯餅了 !

Hash Table

• 一種儲存 Key-Value pair 的 mapping 關係的資料結構
  Key-Value pair，可以用Array實作，利用Array的index作為key，將value存放進去，但是Array就是需要事先宣告Array大小，Hash table 能解決這個問題。
• 目標是: Key的數量，就是Table的size -> Table的size= Θ(Key的數量)
• 透過 Hash function 使得index = function (key)，value就存在table 的index裡。
• 兩筆value存進Table的同一個空格裡，就是發生Collision。
  -> 解決方法 :
  1. 找出table有空位的地方，再把value存進去。
  2. 把存在同一個空格的value，用linkedlist連結起來。